세는 것은 물리적 열거의 번거로운 노동 없이 유한 집합의 크기를 결정하는 예술입니다. 논리적 구조를 활용하면 단순한 메뉴 조합부터 복잡한 암호화 순열에 이르기까지 다양한 문제를 해결할 수 있습니다.
"또는"과 "그리고"의 논리
두 가지 원칙이 조합론 전체 분야를 지탱합니다. 이 원칙의 적용은 작업을 여러 카테고리 중 하나의 선택으로 보는지, 아니면 선택의 연속으로 보는지에 따라 완전히 달라집니다.
덧셈 원리(합의 법칙)
만약 집합 $X$가 서로소인 부분집합 $X_1, X_2, \dots, X_n$로 나뉘어져 있다면, 전체 원소 수 $|X|$는 각 부분집합의 크기 합과 같습니다:
$$|X| = |X_1| + |X_2| + \dots + |X_n|$$
비유: 카이의 빠른 식당에서 주메뉴 메뉴에서 샌드위치를 고르거나, 아포타이저 메뉴에서 아포타이저를 고르는 식사 선택. 둘 다 고를 수 없습니다. 한 가지 항목만 선택해야 합니다.
곱셈 원리(곱의 법칙)
활동이 $t$개의 연속된 단계로 구성되어 있고, 단계 $i$마다 $n_i$개의 가능한 결과가 있다면, 작업을 완료하는 방법의 총 수는 각 단계의 가능성들을 곱한 값입니다:
$$N = n_1 \times n_2 \times \dots \times n_t$$
비유: 빅 페키지 트럭을 구성하세요. 엔진(5가지 옵션)과 캐빈 스타일(3가지 옵션)을 모두 선택해야 합니다. 전체 구성 수는 $5 \times 3 = 15$입니다.
코드 구현 및 복잡도
컴퓨터 과학에서는 이러한 원칙이 반복문 구조로 나타납니다. 순차적인 반복문은 덧셈 원리를, 중첩된 반복문은 곱셈 원리를 나타냅니다.
// 덧셈 원리 (m + n번 실행)
for i = 1 to m: println(i)
for j = 1 to n: println(j)
// 곱셈 원리 (m * n번 실행)
for i = 1 to m:
for j = 1 to n:
println(i, j)
for i = 1 to m: println(i)
for j = 1 to n: println(j)
// 곱셈 원리 (m * n번 실행)
for i = 1 to m:
for j = 1 to n:
println(i, j)
🎯 핵심 원칙
키워드로 구분하세요: "또는"은 덧셈(서로 배타적인 선택)을 의미하고, "그리고" 또는 "연속적인"은 곱셈(순서대로 독립적인 단계)을 의미합니다.